#coding=utf8

import math
import random
import numpy
import copy

def initPopulation(populationSize, chromosomeSize, population):
    for i in xrange(populationSize):
        for j in xrange(chromosomeSize):
            population[i][j] = random.randint(0, 1)

def fit(populationSize, chromosomeSize, population, fitValue, lowerBound, upperBound):
    for i in xrange(populationSize):
        fitValue[i] = 0

    for i in xrange(populationSize):
        for j in xrange(chromosomeSize):
            if population[i][j] == 1:
                fitValue[i] += math.pow(2, j)

        fitValue[i] = lowerBound + fitValue[i] * (upperBound - lowerBound) / (2 ** chromosomeSize - 1)
        fitValue[i] = fitValue[i] + 10 * math.sin(5 * fitValue[i]) + 7 * math.cos(4 * fitValue[i])


def rank(fitValue, population, populationSize, bestFitness, bestIndividual):
    def cmpPopulation(tup1, tup2):
        if tup1[0] < tup2[0]:
            return -1
        elif tup1[0] == tup2[0]:
            return 0
        else:
            return 1


    sortedFitvaluePopulation = sorted(zip(fitValue, population), cmpPopulation)
    fitValue = numpy.array([individualFitness for individualFitness, chromosome in sortedFitvaluePopulation])
    population = numpy.array([chromosome for individualFitness, chromosome in sortedFitvaluePopulation])
    if fitValue[populationSize - 1] > bestFitness:
        return fitValue[populationSize - 1], population[populationSize - 1], fitValue, population
    return bestFitness, bestIndividual, fitValue, population


def select(populationSize, chromosomeSize, population, fitValue):
    fitSum = numpy.zeros([populationSize], int)
    fitSum[0] = fitValue[0]
    for i in xrange(1, populationSize):
        fitSum[i] = fitSum[i - 1] + fitValue[i]

    populationNew = copy.deepcopy(population)
    for i in xrange(populationSize):
        randNum = random.random() * fitSum[populationSize - 1]

        left = 0
        right = populationSize - 1
        while left < right - 1:
            mid = (left + right) / 2
            if randNum > fitSum[mid]:
                left = mid + 1
            else:
                right = mid
        idx = right

        for j in xrange(chromosomeSize):
            populationNew[i][j] = population[idx][j]

        population = populationNew

def crossover(populationSize, chromosomeSize, population, crossRate):
    for i in xrange(0, populationSize, 2):
        randNum = random.random()
        if randNum < crossRate:
            crossPosition = int(randNum * chromosomeSize)
            if crossPosition == 0:
                continue
            for j in xrange(crossPosition, chromosomeSize):
                temp = population[i][j]
                population[i][j] = population[i + 1][j]
                population[i + 1][j] = temp

def mutation(populationSize, chromosomeSize, population, mutateRate):
    for i in xrange(populationSize):
        randNum = random.random()
        if randNum < mutateRate:
            mutatePosition = int(randNum * chromosomeSize)
            if mutatePosition < chromosomeSize:
                population[i][mutatePosition] = 1 - population[i][mutatePosition]


def genetic_algorithm(iterTimes, crossRate, mutateRate):
    lowerBound = 0
    upperBound = 9

    populationSize = (upperBound - lowerBound) * pow(10, 1)
    chromosomeSize = int(math.ceil(math.log(populationSize, 2)))
    population = numpy.zeros([populationSize, chromosomeSize], int)
    fitValue = numpy.zeros([populationSize], float)
    bestFitness = 0
    bestIndividual = numpy.zeros([chromosomeSize], int)

    initPopulation(populationSize, chromosomeSize, population)

    for generation in xrange(iterTimes):
        fit(populationSize, chromosomeSize, population, fitValue, lowerBound, upperBound)
        bestFitness, bestIndividual, fitValue, population = rank(fitValue, population, populationSize, bestFitness, bestIndividual)
        select(populationSize, chromosomeSize, population, fitValue)
        crossover(populationSize, chromosomeSize, population, crossRate)
        mutation(populationSize, chromosomeSize, population, mutateRate)

    q = 0.0
    for j in xrange(chromosomeSize):
        if bestIndividual[j] == 1:
            q += 2 ** j
    q = lowerBound + q * (upperBound - lowerBound) / (2 ** chromosomeSize - 1)

    return q, bestFitness,

print 'genetic_algorithm start ...'
print genetic_algorithm(300, 0.7, 0.1)